Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

Why time limit on test 4?????????!!!!!!!!!!!!!!!
Author: ata
ID: 059912
Problem: 174
Contest: 0
Date: 2014-08-21 08:45:40

#include <bits/stdc++.h>

using namespace std;

const int Maxn=2*1000*100+10;

map<pair<int,int>,int> f1;

int par[Maxn],n;
bool c;

int find_par(int v)
{
if(par[v]==v)
return v;

return par[v]=find_par(par[v]);
}

inline void input()
{
cin>>n;

for(int i=0;i<n;i++)
par[i]=i;

int p=0;
for(int i=0;i<n;i++)
{
pair<int,int> f,l;
cin>>f.first>>f.second>>l.first>>l.second;

if(f1.find(f)!=f1.end()&&f1.find(l)!=f1.end())
{
find_par(f1[f]);
find_par(f1[l]);

if(par[f1[f]]==par[f1[l]])
{
if(!c)
cout<<i+1;
c=true;
}

else
{
par[par[f1[f]]]=par[f1[l]];
find_par(f1[f]);
}

}

else if(f1.find(f)!=f1.end()&&f1.find(l)==f1.end())
{
f1[l]=p++;
par[f1[l]]=find_par(f1[f]);
find_par(f1[l]);
}

else if(f1.find(f)==f1.end()&&f1.find(l)!=f1.end())
{
f1[f]=p++;
par[f1[f]]=find_par(f1[l]);
find_par(f1[f]);
}

else if(f1.find(f)==f1.end()&&f1.find(l)==f1.end())
{
f1[f]=p++;
f1[l]=p++;
par[f1[f]]=f1[l];
}

}

if(!c)
cout<<-1;
}


int main()
{
input();
return 0;
}


see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-09-22 20:57:44Online Contester Team © 2002 - 2016. All rights reserved.