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

WA 18
Author: Khasahyar MirMS
ID: 042830
Problem: 121
Contest: 0
Date: 2012-01-27 13:38:14

does anyone have a counter example for my code?!...

#include <vector>
#include <cstdlib>
#include <iostream>

using namespace std;

#define pb(x) push_back(x)

const int MAXN = 200;
const int MAXM = MAXN*MAXN;

int n;
int m;
int C;
int d[MAXN];
bool mark[MAXM];
int c[MAXN][MAXN];
bool visited[MAXN];
int num[MAXN][MAXN];
vector<int> in[MAXN];

void input();
void check();
void dfs(int x);

int main()
{
input();
C = 1;
for(int i=0; i<n; i++)
if(!visited[i] && (d[i]+(d[i]%2)>2))
dfs(i);
for(int i=0; i<n; i++)
if(!visited[i])
dfs(i);
n--;
check();
for(int i=0; i<n; i++, cout<< 0 << endl)
for(int j=0; j<in[i].size() - (d[i]%2); j++)
cout<< c[i][in[i][j]] << " ";
return 0;
}

void dfs(int x)
{
C = 3 - C;
visited[x] = 1;
int v;
int e;
if(x!=n-1)
for(int i=0; i<in[x].size(); i++)
{
v = in[x][i];
e = num[x][v];
if(!mark[e])
{
mark[e] = 1;
c[v][x] = c[x][v] = C;
dfs(v);
}
}
else
for(int i=0; i+1<n; i++)
if(d[i]%2)
{
e = num[x][i];
if(!mark[e])
{
mark[e] = 1;
dfs(i);
}
}
return;
}

void check()
{
int x;
int y;
int v;
for(int i=0; i<n; i++)
{
x = y = 0;
if(d[i]>1)
{
for(int j=0; j<in[i].size() - (d[i]%2); j++)
{
v = in[i][j];
if(c[i][v]==1)
x++;
else if(c[i][v]==2)
y++;
else
exit(1);
}
if(!x || !y)
{
cout<< "No solution" << endl;
exit(0);
}
}
}
return;
}

void input()
{
cin>> n;
m=0;
int x;
for(int i=0; i<n; i++)
{
x = -1;
while(x)
{
cin>> x;
if(x)
in[i].pb(x-1);
if(x && x-1>i)
{
x--;
d[i]++;
d[x]++;
num[i][x] = num[x][i] = m++;
x++;
}
}
}
for(int i=0; i<n; i++)
if(d[i]%2)
{
in[i].pb(n);
num[i][n] = num[n][i] = m++;
}
n++;
return;
}


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-20 11:12:56Online Contester Team © 2002 - 2016. All rights reserved.